package binary_tree.Heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * @Description:
 * 最大堆的实现
 * 根节点的编号为0，左孩子为2k + 1，右孩子为2k + 2
 * @Author Stark
 * @Date 2022/3/5 15:16
 **/
public class MaxHeap {
    private List<Integer> data;

    //构造方法
    public MaxHeap(){
        this(10);
    }
    public MaxHeap(int size){
        data = new ArrayList<>(size);
    }
    /**
     * 将任意数组堆化
     * @param arr
     */
    public MaxHeap(int[] arr) {
        data = new ArrayList<>(data.size());
        //将数组中的值拷贝进二叉树中
        for(int i:arr){
            data.add(i);
        }
        //从最后一个结点开始下沉
        for (int i = (data.size() - 1) >> 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
    * @Description: 元素添加
    * @Param: [val]
    * @return: void
    */
    public void add(int val){
        data.add(val);
        siftUp(data.size() - 1);
    }
    /**
     * 取出当前最大堆的最大值
     * @return
     */
    public int extractMax() {
        //判空
        if(data.size() == 0){
            throw new NoSuchElementException("The heap is empty!");
        }
        //取出堆顶
        int out = data.get(0);
        //将末尾顶到堆顶
        data.set(0,data.get(data.size() - 1));
        //删除末尾
        data.remove(data.size() - 1);
        //下沉
        siftDown(0);
        return out;
    }
    public int peekMax() {
        if(data.size() == 0){
            throw new NoSuchElementException("The heap is empty!");
        }
        return data.get(0);
    }

    /**
     * 元素的下沉操作
     * @param k
     */
    private void siftDown(int k) {
        //判断是否还存在子树
        while(leftChild(k) < data.size()){
            int child = leftChild(k);
            //存在右子树并且右子树大于左子树,将较大的结点保存
            if(child + 1< data.size() && data.get(child) < data.get(child + 1)){
                child += 1;
            }
            //判断子树的是否小于结点
            if(data.get(child) < data.get(k)){
                break;
            }
            //交换最大的孩子和父节点的值
            swap(k,child);
            //更新父节点,继续下沉
            k = child;
        }
    }

    /**
    * @Description: 元素的上浮操作
    * @Param: [k]
    * @return: void
    */
    private void siftUp(int k) {
        //终止条件:已经走到根结点 || 父节点的值 >= 结点的值
        while(k > 0 && data.get(parent(k)) < data.get(k)){
            //交换当前结点和父节点的值
            swap(parent(k),k);
            //更新坐标
            k = parent(k);
        }
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    private int parent(int k) {
        return (k - 1) >> 1;
    }

    private int leftChild(int k){
        return 2 * k + 1;
    }

    private int rightChild(int k){
        return 2 * k + 2;
    }

    private void swap(int i, int j) {
        int tmp = data.get(i);
        data.set(i,data.get(j));
        data.set(j,tmp);
    }
    public String toString(){
        return data.toString();
    }
}
